#include <iostream>
#include <vector>
using namespace std;

// 横向扫描
//class Solution{
//public:
//    string longestCommonPrefix(const string & str1,const string & str2){
//        // 遍历次数限定为两个字符串中较短的那一个字符串的长度，减少遍历次数提高效率
//        int length = min(str1.size(),str2.size());
//        // 定义一个下标，来标识结尾时要复制的字符串的长度
//        int index = 0;
//
//        // 下标不超过字符串长度 且 当前字符串的第index个字符与下一个字符串的第index个字符相等
//        while (index < length && str1[index] == str2[index]){
//            // 满足上述条件则index自增1
//            index++;
//        }
//
//        // 返回str1(或str2)的前index个字符(substr复制一个指定长度的子字符串)
//        return str1.substr(0,index);
//    }
//
//    string printPrefix(vector<string> strs){
//        if (strs.empty()){
//            return "";
//        }
//
//        // 定义横向扫描初始下标
//        string prefix = strs[0];
//        // 横向遍历次数取决于字符串数组的行数(字符串的个数)
//        for (int i = 0; i < strs.size(); i++) {
//            // 将当前下标对应的字符与下一个下标对应的字符对比，直到下一个字符串的下标超出字符串数组的行数(字符串的个数)
//            prefix = longestCommonPrefix(prefix,strs[i]);
//            // 如果求出的prefix中没有字符
//            if (prefix.empty()){
//                // 则直接跳出循环
//                break;
//            }
//        }
//
//        // 最终返回已经比较结束的字符串prefix
//        return prefix;
//    }
//};

// 纵向扫描
class Solution{
public:
    string longestCommonPrefix(vector<string> strs){
        if (strs.empty()) {
            return "";
        }

        // 定义第一列的长度(每个字符串的开头的字符的个数，保证为最长长度，遍历时能遍历所有字符串指定列的字符)
        int length = strs[0].size();
        // 定义总行数(字符串的个数)
        int count = strs.size();

        // 通过列数i来遍历，最后返回第一行的前i个字符
        for (int i = 0; i < length; i++) {
        // i = 0

        // i = 1

        // i = 2

            // 定义当前列第一个字符
            char c = strs[0][i];
            // c = strs[0][0]

            // c = strs[0][1]

            // c = strs[0][2]

            // 在i列基础上遍历j行(从第二列j=1开始遍历)，限定j小于总行数
            for (int j = 1; j < count; j++) {
            // j = 1
            // j = 2

            // j = 1
            // j = 2

            // j = 1
            // j = 2

                // 若当前列的总字符数个数等于下一列的总字符数个数 或 下一行当前字符不等于当前列字符
                if (i == strs[j].size() || strs[j][i] != c) {
                // 0 == strs[1].size() || strs[1][0] != strs[0][0]  // false
                // 0 == strs[2].size() || strs[2][0] != strs[0][0]  // false

                // 1 == strs[1].size() || strs[1][1] != strs[0][1]  // false
                // 1 == strs[2].size() || strs[2][1] != strs[0][1]  // false

                // 2 == strs[1].size() || strs[1][2] != strs[0][2]  // false
                // 2 == strs[2].size() || strs[1][2] != strs[0][2]  // true

                    // 返回第一行的前i个字符
                    return strs[0].substr(0, i);
                    // strs[0].substr(0,2)
                }
            }
        }

        return strs[0];
    }
};

int main() {
    vector<string> strs = {"flower","flow","flight"};

    Solution s;
//    cout << s.printPrefix(strs) << endl;
    cout << s.longestCommonPrefix(strs) << endl;
}